﻿using System;
using System.Linq;

namespace TextManipulation
{
    /// <summary>
    /// http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance
    /// </summary>
    public static class DamerauLevenshtein
    {
        public static int DamerauLevenshteinDistanceTo(this string srt1, string str2)
        {
            if (String.IsNullOrEmpty(srt1))
            {
                if (!String.IsNullOrEmpty(str2))
                {
                    return str2.Length;
                }

                return 0;
            }

            if (String.IsNullOrEmpty(str2))
            {
                if (!String.IsNullOrEmpty(srt1))
                {
                    return srt1.Length;
                }

                return 0;
            }

            int length1 = srt1.Length;
            int length2 = str2.Length;

            int[,] dist = new int[length1 + 1, length2 + 1];

            for (int i = 0; i <= dist.GetUpperBound(0); i++)
            {
                dist[i, 0] = i;
            }

            for (int i = 0; i <= dist.GetUpperBound(1); i++)
            {
                dist[0, i] = i;
            }

            int cost = 0;
            int del = 0;
            int ins = 0;
            int sub = 0;
            for (int i = 1; i <= dist.GetUpperBound(0); i++)
            {
                for (int j = 1; j <= dist.GetUpperBound(1); j++)
                {
                    if (srt1[i - 1] == str2[j - 1])
                    {
                        cost = 0;
                    }
                    else
                    {
                        cost = 1;
                    }

                    del = dist[i - 1, j] + 1;
                    ins = dist[i, j - 1] + 1;
                    sub = dist[i - 1, j - 1] + cost;

                    dist[i, j] = Math.Min(del, Math.Min(ins, sub));

                    if (i > 1 && j > 1 &&
                        srt1[i - 1] == str2[j - 2] &&
                        srt1[i - 2] == str2[j - 1])
                    {
                        dist[i, j] = Math.Min(dist[i, j], dist[i - 2, j - 2] + cost);
                    }
                }
            }

            return dist[dist.GetUpperBound(0), dist.GetUpperBound(1)];
        }
    }
}